目錄
我們提供的服務有：成都網(wǎng)站設計、成都網(wǎng)站建設、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、海城ssl等。為上1000家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務，是有科學管理、有技術的海城網(wǎng)站制作公司
1.用隊列實現(xiàn)棧
增刪
求棧頂元素
判斷棧為空
2.用棧實現(xiàn)隊列?
增刪
返回隊列開頭的數(shù)據(jù)?
判斷隊列為空
尾言
源碼
隊列實現(xiàn)棧
棧實現(xiàn)隊列
1.用隊列實現(xiàn)棧剛講完棧和隊列，LeetCode上有兩題棧與隊列的互相實現(xiàn)，簡單地講講思路和實現(xiàn)吧。
原題地址：225.用隊列實現(xiàn)棧
題目要求我們用兩個隊列來實現(xiàn)一個棧，我們知道隊列的性質是先進先出，而棧是后進先出，假設隨便給我們要的這個棧之中添加幾個數(shù)，便能畫出這樣的圖
那這樣接下來若要出棧，輸出的便是?5?，但是隊列出隊的話只能輸出?1?。所以我們就要用到另一個隊列，把隊列1最后一個數(shù)前面的數(shù)據(jù)導入到隊列2之后再輸出隊列1的唯一數(shù)。這樣就完成了出棧的模擬。
之后把隊列1第一個數(shù)據(jù)刪除，一定保證一個隊列為空?，即第二次出棧還是要把非空的隊列的數(shù)據(jù)導入空隊列里去。
求棧頂元素若是要入棧操作的話就是直接再非空隊列隊尾插入數(shù)據(jù)就可以了，最后面的值不會被導入到另一隊列里。所以下次出棧就會將其輸出。
找棧頂元素其實與出棧的唯一不同就是，出棧要刪除棧頂元素，而求棧頂元素不一樣，其要求要有返回值。偷懶的話可以先寫求棧頂元素，之后出棧只要復用函數(shù)就可以完成了。
前面講過，必定有一個隊列為空，因此不能只檢查一個隊列而是兩個隊列都要檢查，即兩個隊列都為空則證明棧為空。
原題地址：232.用棧實現(xiàn)隊列
增刪其實只要熟悉了隊列和棧的基本性質，其實這兩題也并不會很難，思路正確了剩下的就只需要注意編寫程序時的小細節(jié)就可以了。?
仔細分析題目，要求用兩個棧實現(xiàn)一個隊列，既然題目都這樣要求了只用一個棧明顯是不可能的，上一題的經(jīng)驗告訴我，要把數(shù)據(jù)導入到另一個棧里。
把數(shù)據(jù)導到另一個棧后我們驚奇的發(fā)現(xiàn)，數(shù)據(jù)恰好就成了我們想要的樣子。這段數(shù)據(jù)就可以直接輸出了。
這下我們就可以讓一個棧專門承載輸入數(shù)據(jù)，另一個棧專門輸出數(shù)據(jù)，輸出棧為空時再從輸入棧把數(shù)據(jù)導入到輸出棧里面。
也是跟刪除是一個道理，不過只是返回值并不刪除數(shù)據(jù)。即輸出棧沒有值就導入輸入棧的值進去就可以了。
兩個棧如果都為空，隊列就為空，只有其中一個棧為空是不算的。
好了，這樣今天我們兩道題的思路與實現(xiàn)到這里就講完了，說實在的用C語言寫確實是麻煩了一點，但是之前寫過棧和隊列的話直接把代碼復制過去，之后用自己之前寫的函數(shù)寫就可以了。有問題的話一定私信或者評論區(qū)指出，一定第一時間回復！?。?/p>源碼 隊列實現(xiàn)棧
重慶分公司
重慶分公司
typedef int Qdatatype;
typedef struct Qnode
{
Qdatatype data;
struct Queue* next;
}Qnode;
typedef struct Queue
{
Qnode* head;
Qnode* tail;
int size;
}Queue;
void Queueinit(Queue* p)
{
p->head = NULL;
p->tail = NULL;
p->size = 0;
}
bool QueueEmpty(Queue* p)
{
assert(p);
return p->head == NULL || p->tail == NULL;
}
void Queuepush(Queue* p, Qdatatype x)
{
assert(p);
Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
if (newnode == NULL)
{
perror(malloc);
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (p->head == NULL)
{
p->head = p->tail = newnode;
p->size++;
}
else
{
p->tail->next = newnode;
p->tail = newnode;
p->size++;
}
}
void Queuepop(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
Qnode* next = p->head->next;
free(p->head);
p->head = next;
p->size--;
}
Qdatatype Queuefront(Queue* p)
{
assert(p);
return p->head->data;
}
void QueueDestroy(Queue* p)
{
assert(p);
Qnode* cur = p->head;
while (cur)
{
Qnode* next = cur->next;
free(cur);
cur = next;
}
p->head = p->tail = NULL;
p->size = 0;
}
Qdatatype Queueback(Queue* p)
{
assert(p);
assert(!QueueEmpty(p));
return p->tail->data;
}
int Queuesize(Queue* p)
{
assert(p);
return p->size;
}
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* stack = (MyStack*)malloc(sizeof(MyStack)); //開辟棧的空間，動態(tài)開辟才不是局部變量
Queueinit(&stack->q1); //兩個隊列的初始化
Queueinit(&stack->q2);
return stack;
}
void myStackPush(MyStack* obj, int x) {
assert(obj);
if (!QueueEmpty(&obj->q1)) //在非空隊列里插入數(shù)據(jù)，兩個都為空則默認插入在第一個里面
{
return Queuepush(&obj->q1, x);
}
else
{
return Queuepush(&obj->q2, x);
}
}
int myStackPop(MyStack* obj) {
assert(obj);
Queue* emptyqueue = &obj->q1; //一定有一個空隊列
Queue* queue = &obj->q2; //一個是有數(shù)據(jù)的隊列
if (QueueEmpty(&obj->q2)) //判斷為空的隊列
{
emptyqueue = &obj->q2;
queue = &obj->q1;
}
while (Queuesize(queue) >1)
{
Queuepush(emptyqueue, Queuefront(queue)); //導入后刪除原隊列里的數(shù)據(jù)
Queuepop(queue);
}
int ret = Queuefront(queue);
Queuepop(queue);
return ret;
}
int myStackTop(MyStack* obj) {
assert(obj);
if (!QueueEmpty(&obj->q1))
{
return Queueback(&obj->q1);
}
else
{
return Queueback(&obj->q2);
}
}
bool myStackEmpty(MyStack* obj) {
assert(obj);
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}typedef int STdatatype;
typedef struct Stack
{
STdatatype* data;
int top;
int capacity;
}Stack;
void checkcapacity(Stack* p)
{
STdatatype* newp;
if (p->top == p->capacity)
{
newp = (STdatatype*)realloc(p->data, sizeof(Stack) * p->capacity * 2);
if (newp == NULL)
{
perror(realloc);
exit(-1);
}
p->data = newp;
p->capacity *= 2;
}
if (p == NULL)
{
perror(realloc);
exit(-1);
}
}
void StackInit(Stack* p)
{
STdatatype* np = (STdatatype*)malloc(sizeof(STdatatype) * 4);
if (np)
{
p->data = np;
}
p->top = 0;
p->capacity = 4;
}
void StackPush(Stack* p, STdatatype x)
{
assert(p);
checkcapacity(p);
(p->data)[p->top] = x;
p->top++;
}
void Stackprint(Stack* p)
{
int i = p->top - 1;
while (i >= 0)
{
printf("%d ", (p->data)[i--]);
}
printf("\n");
}
void StackPop(Stack* p)
{
assert(p);
assert(p->top);
p->top--;
}
STdatatype StackTop(Stack* p)
{
assert(p);
int top = p->top - 1;
return (p->data)[top];
}
int StackEmpty(Stack* p)
{
assert(p);
if (p->top != 0)
{
return 0;
}
return 1;
}
void StackDestroy(Stack* p)
{
assert(p);
assert(p->data);
free(p->data);
p->data = NULL;
p->top = 0;
p->capacity = 0;
}
typedef struct //兩個隊列一個輸出一個輸入，輸出棧里沒數(shù)據(jù)了之后就從輸入里面倒數(shù)據(jù)過去
{
Stack S; //輸入
Stack nullS; //輸出
} MyQueue;
bool myQueueEmpty(MyQueue* obj);
int myQueuePeek(MyQueue* obj);
MyQueue* myQueueCreate() //創(chuàng)建隊列
{
MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue)); //開辟隊列空間
StackInit(&queue->S); //對兩個棧初始化
StackInit(&queue->nullS);
return queue; //返回開辟的隊列
}
void myQueuePush(MyQueue* obj, int x) {
assert(obj);
StackPush(&obj->S, x); //直接在插入的隊列里插入數(shù)據(jù)
}
int myQueuePop(MyQueue* obj) {
assert(obj);
assert(!myQueueEmpty(obj)); //判斷隊列不為空
int ret = myQueuePeek(obj); //取最上面的值返回
StackPop(&obj->nullS); //pop在peek的基礎上增加數(shù)據(jù)的刪除
return ret;
}
int myQueuePeek(MyQueue* obj) { //拿最前面的數(shù)據(jù)
assert(obj);
assert(!myQueueEmpty(obj)); //隊列不為空
if (StackEmpty(&obj->nullS)) //輸出棧為空則倒入數(shù)據(jù)
{
while (!StackEmpty(&obj->S)) //直到輸入棧為空，必定一個棧為空
{
StackPush(&obj->nullS, StackTop(&obj->S)); //取輸入棧最上面導入到輸出棧的最下面
StackPop(&obj->S); //清除輸入棧的數(shù)據(jù)
}
}
return StackTop(&obj->nullS); //返回最上面的值
}
bool myQueueEmpty(MyQueue* obj) {
assert(obj);
return StackEmpty(&obj->nullS) && StackEmpty(&obj->S); //兩個棧都為空則隊列為空
}
void myQueueFree(MyQueue* obj) {
assert(obj);
StackDestroy(&obj->nullS); //銷毀兩個棧
StackDestroy(&obj->S);
free(obj); //銷毀隊列
}你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
