棧、佇列、矩陣、連結串列問題（一）

矩阵链表 · 發表 2018-12-17 11:23:40

摘要：目錄用陣列結構實現大小固定的佇列和棧實現一個特殊的棧，在實現棧的基本功能的基礎上，再實現返回棧中最小元素的操作。如何僅用佇列結構實現棧結構？如何僅用棧結構實現佇列結構？貓狗佇列轉圈列印矩陣 ...

用陣列結構實現大小固定的佇列和棧
實現一個特殊的棧，在實現棧的基本功能的基礎上，再實現返回棧中最小元素的操作。
如何僅用佇列結構實現棧結構？
如何僅用棧結構實現佇列結構？
貓狗佇列
轉圈列印矩陣
旋轉正方形矩陣
反轉單向和雙向連結串列

用陣列結構實現大小固定的佇列和棧

棧的實現：引入一個變數size，表示當前棧結構裡物件的個數（size會一直指向棧頂的上面一個下標，例如棧頂物件在陣列中下標為5，那麼size指向下標6）。棧結構壓入一個物件，size+1；棧結構彈出一個物件，size-1。

public static class ArrayStack{

Integer size;
Integer[] arr;

public ArrayStack(int initSize){
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
arr = new Integer[initSize];
size = 0;
}

public Integer peek(){
if(size == 0){
return null;
}
return arr[size - 1];
}

public void push(int obj){
if(size == arr.length){
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
arr[size++] = obj;
}

public Integer pop(){
if(size == 0){
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
return arr[--size];
}
}

佇列的實現：引入變數size，表示當前佇列中物件的個數；引入變數start，表示佇列頭部的陣列下標，隨著彈出佇列操作進行變化（即當佇列頭部彈出一個物件後，start+1）；引入變數end，表示佇列尾部的陣列下標，隨著加入佇列操作進行變化（即當佇列尾部加入一個物件後，end+1）；當start或者end超出陣列下標時，start或者end等於0，又從陣列0位置開始計算，一直迴圈。

public static class ArrayQueue{

private Integer size;
private Integer start;
private Integer end;
private Integer[] arr;

public ArrayQueue(int initSize){
if (initSize < 0) {
throw new IllegalArgumentException("The init size is less than 0");
}
size = 0;
start = 0;
end = 0;
arr = new Integer[initSize];
}

public Integer peek(){
if(size == 0){
return null;
}
return arr[start];
}

public void push(int obj){
if(size == arr.length){
throw new ArrayIndexOutOfBoundsException("The queue is full");
}
size++;
arr[end] = obj;
end = end == arr.length - 1 ? 0 : end + 1;
}

public Integer pop(){
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("The queue is empty");
}
size--;
int tmp = start;
start = start == arr.length - 1 ? 0 : start + 1;
return arr[tmp];
}

}

實現一個特殊的棧

實現一個特殊的棧，在實現棧的基本功能的基礎上，再實現返

回棧中最小元素的操作。

【要求】

pop、push、getMin操作的時間複雜度都是O(1)。
設計的棧型別可以使用現成的棧結構。

思路：

getMin操作如果是遍歷整個棧，那麼時間複雜度就變成O(N)了，所以需要另外建立一個只存放最小數的棧，最小數棧的個數與實際的棧同步，當實際棧加入一個數，最小數棧就加入當前棧中的最小數，出棧操作同理。

Stack<Integer> stackData = new Stack<>();
Stack<Integer> stackMin = new Stack<>();

public void push(int obj){
if(stackMin.isEmpty()){
stackMin.push(obj);
}else if(stackMin.peek() >= obj){
stackMin.push(obj);
}else{
int num = stackMin.peek();
stackMin.push(num);
}
stackData.push(obj);
}

public Integer pop(){
if (stackData.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
stackMin.pop();
return stackData.pop();
}

public Integer getMin(){
if (stackMin.isEmpty()) {
throw new RuntimeException("Your stack is empty.");
}
return stackMin.peek();
}

如何僅用佇列結構實現棧結構？

思路：建立兩個佇列queue和help，當peek或者pop時，將queue中除末尾以外的全部物件倒入help裡面，返回末尾物件，然後交換兩個佇列的指標。

public static class TwoQueuesStack {

private Queue<Integer> queue;
private Queue<Integer> help;

public TwoQueuesStack(){
queue = new LinkedList<>();
help = new LinkedList<>();
}

public void push(int num){
queue.add(num);
}

public Integer peek(){
if(queue.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
while (queue.size() > 1){
help.add(queue.poll());
}
int res = queue.poll();
help.add(res);
swap();
return res;
}

public Integer pop(){
if(queue.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
while (queue.size() > 1){
help.add(queue.poll());
}
int res = queue.poll();
swap();
return res;
}

private void swap() {
Queue<Integer> tmp = help;
help = queue;
queue = tmp;
}

}

如何僅用棧結構實現佇列結構？

思路：建立兩個棧結構stackPush和stackPop，stackPush負責加入佇列操作，stackPop負責彈出佇列操作。當stackPop為空時，將stackPush中的資料倒入stackPop中。倒入操作需要滿足兩點：

一次倒入操作必須把stackPush中的資料倒完；
必須在stackPop為空時才能倒入資料。

public static class TwoStacksQueue {

private Stack<Integer> stackPush;
private Stack<Integer> stackPop;

public TwoStacksQueue() {
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}

public void push(int pushInt) {
stackPush.push(pushInt);
}

public int peek(){
if(stackPush.isEmpty() && stackPop.isEmpty()){
throw new RuntimeException("Queue is empty!");
}else if(stackPop.isEmpty()){
while (!stackPush.isEmpty()){
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}

public int pop(){
if(stackPush.isEmpty() && stackPop.isEmpty()){
throw new RuntimeException("Queue is empty!");
}else if(stackPop.isEmpty()){
while (!stackPush.isEmpty()){
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}

}

貓狗佇列

已知有寵物、狗、貓類如下，實現一種貓狗佇列的結構，要求實現add、pollAll、pollDog、pollCat、isEmpty、isDogEmpty、isCatEmpty等方法。

class Pet {
private String type;
public Pet(String type) {
this.type = type;
}
public String getType() {
return this.type;
}
}
 
class Dog extends Pet {
public Dog() {
super("Dog");
}
}
 
class Cat extends Pet {
public Cat() {
super("Cat");
}
}

分析：本題考查實現特殊資料結構及針對特殊功能的演算法設計能力。建立一個貓佇列和一個狗佇列，可以解決大部分的需求。

但是由於在pollAll方法中，需要判斷最先加入的貓和最先加入的狗的順序，所以需要在每個寵物加入時加一個類似時間戳的標記。

我們建立一個PetEnterQueue類，用它來替代Pet類，count就代表加入的順序。

public static class PetEnterQueue {
private Pet pet;
private long count;

public PetEnterQueue(Pet pet, long count) {
this.pet = pet;
this.count = count;
}

public Pet getPet() {
return this.pet;
}

public long getCount() {
return this.count;
}

public String getEnterPetType() {
return this.pet.getPetType();
}
}

public static class DogCatQueue {
private Queue<PetEnterQueue> dogQ;
private Queue<PetEnterQueue> catQ;
private long count;

public DogCatQueue() {
this.dogQ = new LinkedList<PetEnterQueue>();
this.catQ = new LinkedList<PetEnterQueue>();
this.count = 0;
}

public void add(Pet pet) {
if (pet.getPetType().equals("dog")) {
this.dogQ.add(new PetEnterQueue(pet, this.count++));
} else if (pet.getPetType().equals("cat")) {
this.catQ.add(new PetEnterQueue(pet, this.count++));
} else {
throw new RuntimeException("err, not dog or cat");
}
}

public Pet pollAll() {
if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
return this.dogQ.poll().getPet();
} else {
return this.catQ.poll().getPet();
}
} else if (!this.dogQ.isEmpty()) {
return this.dogQ.poll().getPet();
} else if (!this.catQ.isEmpty()) {
return this.catQ.poll().getPet();
} else {
throw new RuntimeException("err, queue is empty!");
}
}

public Dog pollDog() {
if (!this.isDogQueueEmpty()) {
return (Dog) this.dogQ.poll().getPet();
} else {
throw new RuntimeException("Dog queue is empty!");
}
}

public Cat pollCat() {
if (!this.isCatQueueEmpty()) {
return (Cat) this.catQ.poll().getPet();
} else
throw new RuntimeException("Cat queue is empty!");
}

public boolean isEmpty() {
return this.dogQ.isEmpty() && this.catQ.isEmpty();
}

public boolean isDogQueueEmpty() {
return this.dogQ.isEmpty();
}

public boolean isCatQueueEmpty() {
return this.catQ.isEmpty();
}

}

轉圈列印矩陣

給定一個整型矩陣matrix，請按照轉圈的方式列印它。

思路：轉圈列印其實可以理解為，將矩陣分為從外到內一圈一圈的矩形，每次只打印一個矩形，那麼只需要找到每個矩形的上下左右四個邊界就可以得到這個矩形。

public static void spiralOrderPrint(int[][] matrix){

int top = 0;
int left = 0;
int bottom = matrix.length - 1;
int right = matrix[0].length - 1;

while (top <= bottom && left <= right){
printEdge(matrix, top++, left++, bottom--, right--);
}

}

public static void printEdge(int[][] matrix, int top, int left, int bottom, int right){

if(top == bottom){
for(int i = left; i <= right; i++){
System.out.print(matrix[top][i] + " ");
}
}else if(left == right){
for(int i = top; i <= bottom; i++){
System.out.print(matrix[i][top] + " ");
}
}else{
int r = left;
int b = top;
while (r != right){
System.out.print(matrix[top][r] + " ");
r++;
}
while (b != bottom){
System.out.print(matrix[b][right] + " ");
b++;
}
while (r != left){
System.out.print(matrix[bottom][r] + " ");
r--;
}
while (b != top){
System.out.print(matrix[b][left] + " ");
b--;
}
}
}

旋轉正方形矩陣

給定一個整型正方形矩陣matrix，請把該矩陣調整成順時針旋轉90度的樣子。

思路：與上題一樣將整個矩陣視為一圈一圈的矩形，由外到內依次旋轉。

public static void rotate(int[][] matrix) {
int top = 0;
int left = 0;
int bottom = matrix.length - 1;
int right = matrix[0].length - 1;

while (top < bottom) {
rotateEdge(matrix, top++, left++, bottom--, right--);
}
}

public static void rotateEdge(int[][] matrix, int top, int left, int bottom, int right) {

int times = right - left;
int tmp = 0;
for(int i = 0; i < times; i++){
tmp = matrix[top][left+i];
matrix[top][left+i] = matrix[bottom-i][left];
matrix[bottom-i][left] = matrix[bottom][right-i];
matrix[bottom][right - i] = matrix[top+i][right];
matrix[top+i][right] = tmp;
}

}

反轉單向和雙向連結串列

private class Node{
public int value;
public Node next;

public Node(int data) {
this.value = data;
}
}

private static Node reverseList(Node head){

Node pre = null;//上一個節點
Node next = null;//下一個節點

if(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}

public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;

public DoubleNode(int data) {
this.value = data;
}
}

private static DoubleNode reverseList(DoubleNode head){

DoubleNode pre = null;
DoubleNode next = null;

if(head != null){
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}

參考資料：牛客網左程雲初級演算法教程