栈与队列基本 *** 作

栈与队列基本 *** 作

未完待续

目录

一.栈

1.顺序栈 *** 作：

① 顺序栈的创建（初始化）：

②判断栈是否满了/空：

③顺序栈入栈：

④得到栈顶元素（不d出，仅获得）：

⑤d出栈顶元素： 

顺序栈 示例：

2.链栈

①链栈创建（初始化）：

②判断栈是否为空：

 ③入栈：

④得到栈顶元素（不d出） ：

⑤d出栈顶元素：

链栈示例：

---

 

一.栈 1.顺序栈 *** 作：

注：

1.顺序栈的栈顶top始终为最后一给入栈元素的后一位置

2.所以当top==base时栈空

3.同类型连续地址可以直接相减，结果自动转换为元素个数，所以可知一个栈的大小为top-base

4.该栈相关：

struct ele {
    int data;
};
struct Sqstack {
    ele* base = 0;
    ele* top = 0;
    int maxsize = MAX;
    int nowsize = top - base;
};

① 顺序栈的创建（初始化）：

Sqstack& sqstack_creat() {//返回一个顺序栈结构体
    Sqstack s;
    s.base = new ele [MAX];//new返回首地址
    s.top = s.base;
    return s;
}

②判断栈是否满了/空：

满：

bool sqstack_f(Sqstack& s) {//判断栈是否满了
    if (s.top - s.base == s.maxsize) return 1;
    return 0;
}

空： 

bool sqstack_emp(Sqstack& s) {//判断栈是否满了
    if (s.top - s.base == 0) return 1;
    return 0;
}

③顺序栈入栈：

bool sqstack_push(Sqstack& s,ele e) {//向s顺序栈推入e元素
    //因为top指向尾元素的下一位置，所以这里先给top位置赋值，在自加
    if (s.top - s.base == s.maxsize) return 0;//栈满返回0
    *s.top = e;
    s.top++;
    return 1;//添加成功返回1
}

④得到栈顶元素（不d出，仅获得）：

ele sqstack_get(Sqstack s) {//得到栈顶元素（不d出）
    if (s.top - s.base != 0)
    return *(s.top - 1);
}

⑤d出栈顶元素： 

ele sqstack_pop(Sqstack& s) {//d出栈顶元素（显示并删除）
    if (s.top - s.base != 0)
        return *(--s.top);
}

顺序栈 示例：

int main()
{
    int n;
    Sqstack s = sqstack_creat();//创建顺序栈
    ele e;
    cin >> n;
    e.data = n;
    cout << "此时判断栈空的返回值为" << " " << sqstack_emp(s) << endl;
    sqstack_push(s, e);//推入e元素
    cout << "推入元素 e.data = " << n< 
 
2.链栈 
注：
 
1.链栈即为用链表表示的栈，此时定义头节点为栈顶（元素的地址）——即最后入栈的元素
 
2.因为头节点为栈顶，所以空栈时头节点为空指针，创建的时候初始化即可
 
3.头节点（栈顶）为空的时候空栈
 
***4.一个重要的 *** 作：接下来的函数内部可能需要独立改变头节点（栈顶的地址），但是如果只用传进的参数来修改无法真正的对地址进行修改。所以采用引用地址的 *** 作。
 
例把在函数里使head地址变为为head->next：
 
void test(linkstack*& head) {//对地址head引用
    head = head->next;
}
 
 
 
该栈相关：
 
struct ele {
    int num;
};
struct linkstack {
    ele data ;
    linkstack* next=0 ;
};
 
 
①链栈创建（初始化）： 
linkstack* linkstack_creat() {//创建一个空栈，返回头节点（栈顶）
    linkstack* q = 0;
    return q;
}
 
②判断栈是否为空： 
bool linkstack_emp(linkstack* head) {
    if (head == 0)
        return 1;
    return 0;
}
 
 ③入栈： 
linkstack*  linkstack_push(linkstack*& head, ele e) {//推入e元素(注意引用
    linkstack* temp = new linkstack;
    temp->data = e;
    temp->next = head;
    head = temp;//****注意引用，不然 *** 作无效
    return head;
}
 
④得到栈顶元素（不d出） ： 
ele  linkstack_get(linkstack* head) {//获得栈顶元素（不d出）
    if(head!=0)
    return head->data;
}
 
⑤d出栈顶元素： 
ele linkstack_pop(linkstack*& head) {
    linkstack* temp1 = head;//保留原地址， *** 作完释放
    ele temp2 = head->data;
    head = head->next;
    delete temp1;
    return temp2;
}
 
 
链栈示例： 
#include 
using namespace std;

struct ele {
    int num;
};
struct linkstack {
    ele data ;
    linkstack* next=0 ;
};
linkstack* linkstack_creat() {//创建一个空栈，返回头节点（栈顶）
    linkstack* q = 0;
    return q;
}
bool linkstack_emp(linkstack* head) {
    if (head == 0)
        return 1;
    return 0;
}
linkstack*  linkstack_push(linkstack*& head, ele e) {//推入e元素(注意引用
    linkstack* temp = new linkstack;
    temp->data = e;
    temp->next = head;
    head = temp;//****注意引用，不然 *** 作无效
    return head;
}
ele  linkstack_get(linkstack* head) {//获得栈顶元素（不d出）
    if(head!=0)
    return head->data;
}
ele linkstack_pop(linkstack*& head) {
    linkstack* temp1 = head;
    ele temp2 = head->data;
    head = head->next;
    delete temp1;
    return temp2;
}
int main()
{
    int n;
    linkstack* s = linkstack_creat();//创栈
    ele e;
    cin >> n;
    e.num = n;
    cout << "此时判断栈空的返回值为" << " " << linkstack_emp(s) << endl;
    linkstack_push(s, e);//推入e元素
    cout << "推入元素 e,e.num = " << n< 
 
 
 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5718496.html