数据结构-栈,队列

0PTA截图

数据结构-栈,队列

1本周学习总结

1.1栈

数据结构-栈,队列
栈式一种只能在一端进行插入或删除操作的线性表,表中允许插入、删除操作的一端为栈顶。
栈中元素特性:具有线性关系,后进先出
进出栈规则:栈顶出栈,栈底最后出栈;时进时出,元素未完全进栈时,即可出栈。

  • 顺序栈
    顺序栈四要素
    1、栈空:top=-1
    2、栈满:top=MaxSize-1
    3、进栈e操作:top++;st->data[top]=e
    4、退栈操作:e=st->data[top];top--
    操作函数
    结构体
typedef struct
{
    ElemType data[MaxSize];
    int top;//栈顶指针
}Stack;
typedef Stack *SqStack;

1、初始化

void InitStack(&s)
{
    s=new Stack;
    s->top=-1;
}

2、销毁栈

void DestroyStack(SqStack &s)
{
    delete s;
}

3、判断栈空

bool StackEmpty(s)
{
    return(s->top==-1)
}

4、创建栈

Stack CreateStack(int MaxSize)
{
    Stack s=(Stack)malloc(sizeof(struct SNode));
    s->Data=(ElementType *)malloc (MaxSize*sizeof(ElementType));
    s->top=0;
    s->MaxSize = MaxSize;
    return s;
}

5、进栈

bool Push (SqStack &s,ElemtType e)
{
    if(s->top==MaxSize-1)//顺序栈务必考虑栈满
    return false;
    s->top++;//顶指针增1
    s->Data[s->top]=e;
    return true;
}

6、出栈

bool Pop(SqStack &s,ElemType &e)
{
    if(s->top==-1)//栈为空,栈下益出
    return false';
    e=s->Data[s->top];//取栈顶指针元素
    s->top--;
    return true;
}

链栈

数据结构-栈,队列

采用链表存储结构称为链栈

  • 链栈的结构体
typedef int ElemType;
typedef struct Linknode
{
    ElemType data;//数据域
    struct Linknode *next;//指针域
}LinkNode, *LiStack;
  • 栈的四要素
    1、栈空:s->next==NULL;
    2、栈满:不考虑
    3、进栈e操作:节点插入到头节点后,链表头插法
    4、退栈操作:取出头节点之后节点的元素并删除
  • 栈的基本运算
    1、初始化栈
void InitStack(LiStack &s)
{
    s=new LiNode;
    s->next=NULL;
}

2、销毁栈

void DestroyStack(LiStack &s)
{
    LiStack node;
    whilw(s!=NULL)
    {
      node=s;
      s=s->next;
      delete node;
     }
}

3、判断栈是否为空

bool StackEmpty(LiStack &s)
{
    return (s->next==NULL);
}

4、进栈

void Push (LiStack &s)
{
    LiStack p;
    p=new LiNode;
    p->data=e;
    p->next=s->next;
    s->next=p;
}

5、出栈

bool pop(LiStack &s,ElemType &e)
{
    LiStack p;
    if(s->next==NULL)
    return false;
    p=s->next;
    e=p->data;
    s->next=p->next;
    delete p;
    return true;
}

6、取栈顶元素

bool GetTop(LiStack s,ElemType &e)
{
    if(s->next==NULL)
    return false;
    e=s->next->data;
    return true;
}

1.2栈的应用

  • 表达式
    数据结构-栈,队列
    本题的测试点有一个比较难想到:第一个数为正数,且带有正号,则不输出;中间的数为正数也带有正号,但输出不带正号
#include <iostream>
#include<stack>
using namespace std;
stack<char>s;
char str[1000];
int main()
{
	int i = 0,flag=0;
	cin >> str;
	for (; str[i] != '\0'; i++)
	{
		if ((i == 0 && (str[i] == '-'||str[i]=='+')) || (i>=1&&str[i - 1] == '(' &&( str[i] == '-'||str[i]=='+')))//判断负号
		{
            if(str[i]=='+'&&i==0){
                flag = 0;
            }
            else if(str[i]=='+'){
                cout<<" ";flag=0;
            }
			else if (flag == 0)cout << str[i];
			else cout << " " << str[i];
			flag = 0;
		}
		else if (str[i] == '+' || str[i] == '-') {//+或-
			while (!(s.empty()||s.top() == '('))
			{
				cout << " " << s.top();
				s.pop();
			}
			s.push(str[i]);
		}
		else if (str[i] == '*' || str[i] == '/')
		{
			while (!s.empty() && (s.top() == '/' || s.top() == '*'))
			{
				cout << " " << s.top();
				s.pop();
			}
			s.push(str[i]);
		}
		else if (str[i] == '(')s.push(str[i]);
		else if (str[i] == ')') {
			while (s.top() != '(')
			{
				cout << " " << s.top();
				s.pop();
			}
			s.pop();
		}
		//  3*(-4)
		else if ((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
		{
			if (flag)cout << " ";
			while ((str[i] >= '0' && str[i] <= '9') || str[i] == '.')
			{
				 cout << str[i];
				i++;
			}
			i--;
			flag = 1;
		}
		
	}

	while (!s.empty())
	{
		cout << " " << s.top();
		s.pop();
	}

	return 0;
}

1.3队列

数据结构-栈,队列

只允许在表的一段进行插入,而在表的另一端进行删除的线性表。
队尾(rear)--允许插入的一端
队头(front)--允许删除的一端
队列特点:先进先出
应用:操作系统,销售系统,打印机,手机短信发送

  • 顺序队
    顺序队四要素(初始时 front=rear=-1)
    1、队空:front=rear;
    2。队满:rear=MaxSize-1;
    3、元素e进队:raer++;data[rear]=e;
    4、元素e出队:front++;e=data[front];
    结构体
typedef struct
{
    ElemType data[MaxSize];
    int front,rear;//队首和队尾指针    
}Queue;
typedef Queue *SqQueue;

1、初始化

void InitQueue(SqQueue &q)
{
    q=new Queue;
    q->front=q->rear=-1;
}

2、销毁队列

void DestroyQueue(SqQueue &q)
{
    delete q;
}

3、判断队列是否为空

bool QueueEmpty(SqQueue q)
{    
    return (q->front==q->rear);
}

4、进队列

bool enQueue(SqQueue &q,ElemType e)
{
    if(q->rear+1==MaxSize)
    return false;
    q->rear=q->rear+1;
    q->data[q->rear]=e;
    return true;
}

5、出队列

bool deQueue(SqQueue &q,ElemType &e)
{
    if(q->front==q->rear)
    return false;
    q->front=q->front+1;
    e=q->data[q->front];
    return true;
}
  • 环形队列
    数据结构-栈,队列

把存储队列元素的表从逻辑上看成一个环。

  • 操作函数
    1、初始化
void InitQueue(SqQueue &q)
{
    q=new Queue;
    q->front=q->rear=0;
}

2、队满:(rear+1)%MaxSize=front;
3、队空:front=rear;
4、入队

bool enQueue(SqQueue &q,ElemType e)
{
    if((q->rear+1)%MaxSize==0)
    return false;
    q->rear=(q->rear+1)%MaxSize;
    q->data[q->rear]=e;
    return true;
}

5、出队

bool deQueue(SqQueue &q,ElemType &e)
{
    if(q->front==q->rear)
    return false;
    q->front=(q->front+1)%MaxSize;
    e=q->data[q->front];
    return true;
}
  • 队列应用
    舞伴问题
    数据结构-栈,队列
    本题应该使用循环队列,否则或答案错误
int QueueLen(SqQueue Q)//队列长度 
{
    return (Q->rear - Q->front);
}
int EnQueue(SqQueue& Q, Person e)//加入队列
{
    if (Q->rear == MAXQSIZE - 1)
        return false;
    Q->data[(++Q->rear)%MAXQSIZE] = e;
    return true;
}
int QueueEmpty(SqQueue& Q)//队列是否为空 
{
    if (Q->front == Q->rear)
        return 1;
    return 0;
}
int DeQueue(SqQueue& Q, Person& e)//出队列
{
    if (Q->front == Q->rear)
        return false;
    (++Q->front)%MAXQSIZE;
    e = Q->data[Q->front];
    return true;
}
void DancePartner(Person dancer[], int num) //配对舞伴 
{
    Person p;
    int i;
    for (i = 0; i < num; i++)
    {
        p = dancer[i];
        if (p.sex == 'M')
        {
            EnQueue(Mdancers, p);

        }
        else
            EnQueue(Fdancers, p);
    }
    while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers))
    {
        DeQueue(Fdancers, p);
        cout << p.name << "  ";
        DeQueue(Mdancers, p);
        cout << p.name <<endl;
    }
    return ;
}

2PTA实验作业

2.1符号配对

**思路及伪代码
定义一个字符类型的栈;和字符串型的leftchar,rightchar分别存放左右括号;令flag=0;当输入的字符不为空时,利用 stack库里的find函数,若左右括号都存在,flag=1;如果栈空且有右括号存在,return false;如果配对成功,出栈;否则进栈;如果flag=1且栈空,return true;否则如果flag=1,输出栈顶元素,return false;否则 return true;

	stack <char> st;
	string leftchar = "([{";
	string rightchar = ")]}";
	int i;
	int flag = 0;
	char str = bracket_str[i++];
	while(str)
		if leftchar.find(str) != -1 || rightchar.find(str) != -1//左括号和右括号都存在
		then
			flag = 1;
			if st.empty() && rightchar.find(str) != -1//栈空,有右括号
                            then
				return false;
			else if !st.empty() && rightchar.find(str) != -1&&rightchar.find(str)==leftchar.find(st.top())//配对成功
                              then
				st.pop();
                                end if
			else
				st.push(str);
		end if
		str = bracket_str[i++];
	end if
	if flag && st.empty()
            then 
		return true;
             end if
	else if flag
	   then
		cout << st.top()<<"\n";
		return false;
	    end else if 
	else
		return true;

用到了stack库里的find(找) empty(判断空) push(进栈) pop(出栈) top(取栈顶元素)函数,使代码更加简洁,提高了效率,利用了栈这一结构存放符号

2.2银行排队

  • 思路
    利用for循环,将用户的编号输入,并利用%判断奇数或偶数,奇数排到A对队列,偶数排到B队列。解决输出问题,若A不为空则直接输出,否则输出B。利用while循环,当两个中有不为空的时候输出前面带有空格的数据。
	int num;//顾客人数
	int i;
	int temp;//顾客编号
	cin >> num;
	queue<int>A, B;
	for  i = 0 to num-1
	
		cin >> temp;
		if (temp % 2)//偶数
                    then
			A.push(temp)
                    end if
		else
			B.push(temp)
	
	int flag = 0;
	if !A.empty()
	
	      then	
		cout << A.front();
		A.pop();
		i = 1;
	      end if
	else
			cout << B.front();
		B.pop();
	end else
	while !A.empty() || !B.empty()
	
		i++;
		if i % 2
		then
			if !A.empty()
			then
				cout <<" "<< A.front();
				A.pop();
			end if
		end if
		else
		
			if !A.empty())
			then
				cout << A.front();
				A.pop();
			end if
			if !B.empty()
			then
				cout <<" "<< B.front();
				B.pop();
			end if
		
	end while
	

3阅读代码

数据结构-栈,队列

  • 思路:
    从队列尾部插入元素时,我们可以提前取出队列中所有比这个元素小的元素,使得队列中只保留对结果有影响的数字。这样的方法等价于要求维持队列单调递减,即要保证每个元素的前面都没有比它小的元素。

  • 代码
    数据结构-栈,队列

  • 时间复杂度
    O(1)(插入,删除,求最大值)
    删除操作于求最大值操作显然只需要 O(1) 的时间。
    而插入操作虽然看起来有循环,做一个插入操作时最多可能会有 n 次出队操作。但要注意,由于每个数字只会出队一次,因此对于所有的 n 个数字的插入过程,对应的所有出队操作也不会大于 n次。因此将出队的时间均摊到每个插入操作上,时间复杂度为 O(1)。

  • 空间复杂度
    O(n),需要用队列存储所有插入的元素

  • 难点
    如何高效实现一个始终递减的队列?
    只需要在插入每一个元素 value 时,从队列尾部依次取出比当前元素 value 小的元素,直到遇到一个比当前元素大的元素 value' 即可。

  • 优势
    从队列尾部取出元素,因此需要使用双端队列来实现。另外我们也需要一个辅助队列来记录所有被插入的值,以确定 pop_front 函数的返回值。

保证了队列单调递减后,求最大值时只需要直接取双端队列中的第一项即可。

上一篇:PTA 浙大版《数据结构(第2版)》题目集 习题3.5 求链表的倒数第m个元素 (20 分)


下一篇:数据结构