棧和隊列

1. 棧

棧：?種特殊的線性表，其只允許在固定的?端進?插?和刪除元素操作。進?數據插?和刪除操作 的?端稱為棧頂，另?端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。 壓棧：棧的插?操作叫做進棧/壓棧/?棧，?數據在棧頂。 出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

底層結構選型 棧的實現?般可以使?數組或者鏈表實現，相對??數組的結構實現更優?些。因為數組在尾上插? 數據的代價?較?。

棧的實現

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int STDataType;typedef struct Stack
{STDataType* PST;int top;int capasity;
}Stack;typedef struct MyQueue {Stack pushst;Stack popst;
} MyQueue;
//棧的實現
void StackInit(Stack* ST);
void StackDestroy(Stack* ST);
void StackPush(Stack* ST, STDataType x);
void StackPop(Stack* ST);
void StackPrint(Stack* ST);
int StackIsEmpty(Stack* ST);
STDataType StackTop(Stack* ST);

#include"Stack.h"
//棧的實現
void StackInit(Stack* ST)
{assert(ST);ST->capasity = 4;ST->top = 0;ST->PST =(STDataType*)malloc(sizeof(STDataType)*4);
}
int StackIsEmpty(Stack* ST)
{assert(ST);if (ST->top == 0) {return 1;}else {return 0;}
}
void StackDestroy(Stack* ST)
{assert(ST);free(ST->PST);ST->capasity = 0;ST->top = 0;ST->PST = NULL; 
}
void StackPush(Stack* ST, STDataType x)
{assert(ST);if (ST->top == ST->capasity) {STDataType* temp = (STDataType*)realloc(ST->PST, sizeof(STDataType) * 2 * ST->capasity);if (temp == NULL) {printf("realloc failed\n");exit(1);}ST->PST = temp;ST->capasity = 2 * ST->capasity;}ST->PST[ST->top] = x;ST->top++;
}
void StackPop(Stack* ST)
{assert(ST);if (ST->top) {ST->top--;}
}
void StackPrint(Stack* ST)
{assert(ST);for (int i = 0; i < ST->top; i++){printf("%d ", ST->PST[i]);}printf("top:%d capacity:%d", ST->top,ST->capasity);printf("\n");
}STDataType StackTop(Stack* ST)
{assert(ST);assert(ST->top);return ST->PST[ST->top-1];
} 

最小棧(棧實戰應用)

包含min函數的棧牛客題霸牛客網

//解題思路：1 再搞一個棧2來存儲當前棧1中最小的元素，棧2的棧頂元素就是當前棧1中的最小元素，當棧1最小元素出棧時，棧2也要跟著出棧
2 不要額外棧，把棧存儲的元素類型改為pair類型<棧元素，當前元素到棧底的最小元素>
class Solution {
public:void push(int value) {if(s1.empty()){s1.push({value,value});}else {if(value<=s1.top().second){s1.push({value,value});}else {s1.push({value,s1.top().second});}}}void pop() {s1.pop();}int top() {return s1.top().first;}int min() {return s1.top().second;}stack<pair<int,int>> s1;
};

2. 隊列

概念：只允許在?端進?插?數據操作，在另?端進?刪除數據操作的特殊線性表，隊列具有先進先 出FIFO(First In First Out) ?隊列：進?插?操作的?端稱為隊尾 出隊列：進?刪除操作的?端稱為隊頭

隊列的實現

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int QNDataType;
typedef struct QueueNode {struct QueueNode* next;QNDataType data;}QN;typedef struct Queue {QN* head;QN* tail;
}Queue;void QueueInit(Queue* Qe);
void QueuePrint(Queue* Qe);
void QueuePush(Queue* Qe, QNDataType x);//隊尾入
void QueuePop(Queue* Qe);//隊頭出
QNDataType QueueFront(Queue* Qe);//取隊頭數據
QNDataType QueueBack(Queue* Qe);//取隊尾數據
int QueueSize(Queue* Qe);//取隊列大小
int QueueIsEmpty(Queue* Qe);//判斷隊列是否為空
void QueueDestroy(Queue* Qe);

#include"Queue.h"void QueueInit(Queue* Qe)
{Qe->head = NULL;Qe->tail = NULL;
}
void QueueDestroy(Queue* Qe)
{assert(Qe);QN* cur = Qe->head;while (cur != NULL) {QN* next = cur->next;free(cur);cur = next;}Qe->tail = Qe->head = NULL;}
int QueueIsEmpty(Queue* Qe)//判斷隊列是否為空
{assert(Qe);return Qe->head == NULL;}
void QueuePrint(Queue* Qe)
{assert(Qe);QN* cur = Qe->head;while (cur!= NULL) {printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
void QueuePush(Queue* Qe, QNDataType x)
{assert(Qe);QN* temp = (QN*)malloc(sizeof(QN));if (temp == NULL) {printf("malloc failed\n");exit(-1); }temp->data = x;temp->next = NULL;if (Qe->tail == NULL) {//第一次入數據Qe->head = temp;Qe->tail = temp;}else {//第二次Qe->tail->next = temp;Qe->tail = temp;}
}
void QueuePop(Queue* Qe)
{assert(Qe);assert(Qe->head);if (Qe->head->next == NULL) {//只有一個節點的時候出數據free(Qe->head);Qe->head = Qe->tail = NULL;}else {//多節點出數據QN* next = Qe->head->next;free(Qe->head);Qe->head = next;}
}QNDataType QueueFront(Queue* Qe)//取隊頭數據
{assert(Qe);assert(Qe->head);//判斷隊頭為空return Qe->head->data;
}QNDataType QueueBack(Queue* Qe)//取隊尾數據
{assert(Qe);assert(Qe->head);//判斷隊頭為空return Qe->tail->data;
}int QueueSize(Queue* Qe)//取隊列大小
{assert(Qe);QN* cur = Qe->head;int size = 0;while (cur!=NULL) {size++;cur = cur->next;}return size;}