C語言近萬字為你講透棧和隊列
更新時間：2022年05月26日 10:11:43 作者：披星戴月的賈維斯
對于線性表，我們可能要執(zhí)行下列操作：訪問表的第k個結(jié)點、在k這個結(jié)點之前或者之后插入一個新結(jié)點，抑或是刪除第k個結(jié)點等等操作，其中我們會遇到值對第一個或者最后一個結(jié)點插入、刪除、和訪問值的線性表，我們給它們以特殊的名稱：棧、隊列、雙端隊列
一、棧與隊列以及雙端隊列的概念
1.1 棧的概念及結(jié)構(gòu)
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的一端 稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂
1.2 隊列的概念及結(jié)構(gòu)
隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出 FIFO(First In First Out)
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
1.3 雙端隊列的概念及結(jié)構(gòu)
雙端隊列：是一種線性表，又稱為雙向隊列，所有的插入和刪除（通常還有所有的訪問）都在表的兩端進行。
二、棧的實現(xiàn)和模擬棧
棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的 代價比較小。、
2.1 實現(xiàn)一個支持動態(tài)增長的棧
頭文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int STDataType;
typedef struct Stack//動態(tài)棧
{
int *a;
int top;//棧頂?shù)奈恢?
int capacity;//容量
}ST;
STDataType StackTop(ST* ps);//返回棧頂?shù)闹?
void StackInit(ST* ps);//初始化棧
void StackDestory(ST* ps);//銷毀棧
void StackPop(ST* ps);//彈出
void StackPush(ST* ps, STDataType x);//插入
bool StackEmpty(ST* ps);//判斷棧是否為空。源文件：
#include"Stack.h"
void StackInit(ST* ps)//棧的初始化
{
assert(ps);
ps->a = NULL;//a點的值指向空
ps->top = 0;//棧底為0
ps->capacity = 0;//空間為0
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);//把a釋放掉
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//入數(shù)據(jù)
{
assert(ps);
//滿了就擴容
if (ps->top == ps->capacity)//如果棧的棧頂恰好和容量相等就擴容
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newCapacity;//新的空間賦給舊的
}
ps->a[ps->top] = x;//棧頂插入x;
ps->top++;//top++
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
--ps->top;//top--就相當(dāng)于刪除操作
}
bool StackEmpty(ST* ps)
{
assert(ps);
//兩種寫法
//if (ps->top > 0)
//{
// return false;
//}
//else
//{
// return true;
//}
return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];//訪問棧頂元素（這里因為top我們設(shè)為0，所以訪問棧頂元素相當(dāng)于top-1
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}2.2 數(shù)組模擬靜態(tài)棧
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int stk[N];
int top = - 1;
int main ()
{
cin >> n;
while(n --)
{
string s;
cin >> s;
if(s == "push")
{
int a;
cin >> a;
stk[++top] = a;
}
if(s == "pop")
{
top--;
}
if(s == "empty")
{
if(top >= 0) printf("NO\n");
else printf("YES\n");
}
if(s == "query")
{
printf("%d\n", stk[top]);
}
}
return 0;
}三、 隊列的實現(xiàn)(動態(tài))和模擬靜態(tài)隊列
隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù) 組頭上出數(shù)據(jù)，效率會比較低。
3.1 實現(xiàn)一個支持動態(tài)增長的棧
頭文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;//方便改類型
typedef struct QueueNode//保存每個節(jié)點的數(shù)據(jù)
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
//上面的寫法等價于：
//typedef struct Queue
//{
// QNode* head;
// QNode* tail;
//};
//
//typedef struct Queue Queue;//
//一般實際情況哨兵位的頭節(jié)點不存儲值，不放數(shù)據(jù)
void QueueInit(Queue* pq);//隊列初始化
void QueueDestory(Queue* pq);//隊列銷毀
void QueuePush(Queue* pq, QDataType x);//隊尾插入
void QueuePop(Queue* pq);//彈出隊頭
bool QueueEmpty(Queue* pq);//判斷是否為空
size_t QueueSize(Queue* pq);//size_t相當(dāng)于Unsinged int
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);源文件：
#include"Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;//先記錄下一個位置
free(cur);//free掉cur指針
cur = next;//cur賦值到下一個位置
}
pq->head = pq->tail = NULL;//置空
}
void QueuePush(Queue* pq, QDataType x)//隊尾插入//插入int類型的參數(shù)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;//新的節(jié)點的值被賦與x
newnode->next = NULL;//新的節(jié)點是在隊尾，所以指向的下一個位置是空
if (pq->tail == NULL)//如果鏈表的第一個值為空，則head = tail = NULL
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else//尾插
{
pq->tail->next = newnode;//先改指向
pq->tail = newnode;//再改地址
}
}
void QueuePop(Queue* pq)//彈出隊首
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)//只有一個節(jié)點
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;//QNode* next相當(dāng)于是QDataType的頭指針的下一個位置
free(pq->head);
pq->head = next;//頭往后走
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->head == NULL && pq->tail == NULL;
return pq->head == NULL;//程序調(diào)試了快一個小時就是因為pq->head沒加后面的== NULL
}
size_t QueueSize(Queue* pq)//size_t相當(dāng)于Unsinged int
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)//返回隊頭第一個位的值
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)//返回隊尾的值
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}3.2 數(shù)組模擬靜態(tài)隊列
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int n;
int hh ,tt = -1;//hh表示頭，tt表示尾
int main ()
{
cin >> n;
while(n --)
{
string s;
cin >> s;
if(s == "push")
{
int x;
cin >> x;
q[++tt] = x;
}
else if(s == "pop")
{
hh ++;
}
else if(s == "empty")
{
if(hh <= tt) printf("NO\n");//尾在邏輯上要比頭更前面
else printf("YES\n");
}
else cout << q[hh] << endl;
}
return 0;
}四、leetcode-棧實現(xiàn)隊列和用隊列實現(xiàn)棧
225. 用隊列實現(xiàn)棧 - 力扣（LeetCode）
代碼：
typedef int QDataType;
typedef struct QueueNode//保存每個節(jié)點的數(shù)據(jù)
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePush(Queue* pq, QDataType x);//隊尾插入
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
size_t QueueSize(Queue* pq);//size_t相當(dāng)于Unsinged int
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;//先記錄下一個位置
free(cur);//free掉cur指針
cur = next;//cur賦值到下一個位置
}
pq->head = pq->tail = NULL;//置空
}
void QueuePush(Queue* pq, QDataType x)//隊尾插入
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)//如果鏈表的第一個值為空，則head = tail = NULL
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else//尾插
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Queue* pq)//彈出隊首
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)//只有一個節(jié)點
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;//QNode* next相當(dāng)于是QDataType的頭指針的下一個位置
free(pq->head);
pq->head = next;//頭往后走
}
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->head == NULL && pq->tail == NULL;
return pq->head == NULL;//程序調(diào)試了快一個小時就是因為pq->head沒加后面的== NULL
}
size_t QueueSize(Queue* pq)//size_t相當(dāng)于Unsinged int
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Queue* pq)//返回隊頭第一個位的值
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
assert(pst);
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1, x);
}
else
{
QueuePush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
Queue* emptyQ = &obj->q1;//假設(shè)q1為空，q2不為空
Queue* nonEmptyQ = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
emptyQ = &obj->q2;
nonEmptyQ = &obj->q1;
}
//把非空隊列的前N個數(shù)據(jù)導(dǎo)入空隊列，剩下一個刪掉
//就實現(xiàn)了后進先出
while(QueueSize(nonEmptyQ) > 1)
{
QueuePush(emptyQ, QueueFront(nonEmptyQ));
QueuePop(nonEmptyQ);
}
int top = QueueFront(nonEmptyQ);//此時那個非空的隊列只剩下一個數(shù)據(jù)
QueuePop(nonEmptyQ);
return top;
}
int myStackTop(MyStack* obj) {
assert(obj);
if(!QueueEmpty(&obj->q1))//如果q1不為空
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
assert(obj);
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
}232. 用棧實現(xiàn)隊列 - 力扣（LeetCode）棧是后進先出
思路：設(shè)計兩個棧，一個棧專門用來入數(shù)據(jù)，一個棧專門用來出數(shù)據(jù)。
typedef int STDataType;
typedef struct Stack//動態(tài)鏈表
{
int *a;
int top;//棧頂?shù)奈恢?
int capacity;//容量
}ST;
STDataType StackTop(ST* ps);
void StackInit(ST* ps);//初始化棧
void StackDestory(ST* ps);
void StackPop(ST* ps);
void StackPush(ST* ps, STDataType x);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)//入數(shù)據(jù)
{
assert(ps);
//滿了就擴容
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
--ps->top;
}
bool StackEmpty(ST* ps)
{
assert(ps);
//兩種寫法
//if (ps->top > 0)
//{
// return false;
//}
//else
//{
// return true;
//}
return ps->top == 0;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];//訪問棧頂元素
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
typedef struct
{
ST pushST;
ST popST;
} MyQueue;
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
assert(obj);
StackInit(&obj->pushST);//&符要加，要改變結(jié)構(gòu)體里面的內(nèi)容
StackInit(&obj->popST);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->pushST, x);
}
int myQueuePop(MyQueue* obj) {
assert(obj);
//如果popST為空， 把pushST的數(shù)據(jù)拿過來，就符合先進先出的順序了
if(StackEmpty(&obj->popST))//如果ST Pop為空就執(zhí)行
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);//把pushST里的數(shù)據(jù)刪掉
}
}
int front = StackTop(&obj->popST);//記錄棧頂?shù)臄?shù)據(jù)
StackPop(&obj->popST);
return front;
}
int myQueuePeek(MyQueue* obj) {
assert(obj);
//如果popST為空， 把pushST的數(shù)據(jù)拿過來，就符合先進先出的順序了
if(StackEmpty(&obj->popST))//如果ST Pop為空就執(zhí)行
{
while(!StackEmpty(&obj->pushST))
{
StackPush(&obj->popST, StackTop(&obj->pushST));
StackPop(&obj->pushST);//把pushST里的數(shù)據(jù)刪掉
}
}
return StackTop(&obj->popST);
}
bool myQueueEmpty(MyQueue* obj) {
assert(obj);
return StackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);
}
void myQueueFree(MyQueue* obj) {
assert(obj);
StackDestory(&obj->pushST);
StackDestory(&obj->popST);
free(obj);
}總結(jié)
本文分別從（1）棧、隊列以及雙端隊列的概念、（2）棧的實現(xiàn)（動態(tài)）和模擬靜態(tài)棧、（3）隊列的實現(xiàn)（動態(tài)）和模擬靜態(tài)隊列、（4）leetcode-棧實現(xiàn)隊列和用隊列實現(xiàn)棧四個方面對棧和隊列這兩個數(shù)據(jù)結(jié)構(gòu)進行了分析，希望大家讀后能夠有所收獲，也希望大家多多支持。
到此這篇關(guān)于C語言近萬字為你講透棧和隊列的文章就介紹到這了,更多相關(guān)C語言棧和隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
一篇文章帶你了解C++(STL基礎(chǔ)、Vector)
這篇文章主要為大家詳細(xì)介紹了C++ STL基礎(chǔ)，vector向量容器使用方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助2021-08-08
這篇文章主要介紹了 C語言內(nèi)存管理的相關(guān)資料,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-05-05
本文主要介紹了VSCode C/C++多文件編譯配置小結(jié),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
異常處理是C++的一項語言機制,用于在程序中處理異常事件,下面這篇文章主要給大家介紹了關(guān)于C++中異常的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-08-08
匯編語言中有一種移位指令叫做循環(huán)左移（ROL）,下面這篇文章主要給大家介紹了關(guān)于C語言字符串左旋的兩種實現(xiàn)方法,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-02-02
內(nèi)存管理是C++最令人切齒痛恨的問題，也是C++最有爭議的問題，C++高手從中獲得了更好的性能更大的自由，C++菜鳥的收獲則是一遍—遍的檢查代碼和對C++的痛恨，但內(nèi)存管理在C++中無處不在，內(nèi)存泄漏幾乎在每個C++程序中都會發(fā)生，要想成為C++高手，內(nèi)存管理這關(guān)是必須過的2022-04-04
使用C/C++調(diào)用libcurl調(diào)試消息的方式
在使用 C/C++ 調(diào)用 libcurl 進行 HTTP 請求時,有時我們需要查看請求的/應(yīng)答消息的內(nèi)容（包括請求頭和請求體）以方便調(diào)試,libcurl 提供了多種方法來捕獲和輸出這些信息,本文介紹具體的使用方式,需要的朋友可以參考下2025-02-02
所謂函數(shù)模板實際上是建立一個通用函數(shù)，其涵涵素類型額形參類型不具體指定，用一個虛擬的類型來代表，這個通用函數(shù)就稱為函數(shù)模板2013-10-10
C++賦值函數(shù)+移動賦值函數(shù)+移動構(gòu)造函數(shù)詳解
這篇文章主要介紹了C++賦值函數(shù)+移動賦值函數(shù)+移動構(gòu)造函數(shù)詳解，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
這篇文章主要為大家詳細(xì)介紹了Qt自定義美化滑動條的相關(guān)知識,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-11-11